home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2302 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: ts17-13.tor.InfoRamp.Net!pitchl
  2. From: pitchl@tdbank.ca (Lew Pitcher)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: Sat, 20 Jan 1996 02:59:02
  6. Organization: Toronto Dominion Bank
  7. Message-ID: <pitchl.43.0002FC00@tdbank.ca>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>
  9. NNTP-Posting-Host: ts17-13.tor.inforamp.net
  10. X-Newsreader: Trumpet for Windows [Version 1.0 Rev A]
  11.  
  12. In article <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca> Bill Simpson <wsimpson@uwinnipeg.ca> writes:
  13. >From: Bill Simpson <wsimpson@uwinnipeg.ca>
  14. >Subject: quick decision: is n a power of 2?
  15. >Date: Fri, 19 Jan 1996 12:00:01 -0600
  16.  
  17. >Is there a fast way to decide whether a number n is a power of 2?
  18.  
  19. ..snip..
  20.  
  21. >Since I am dealing with unsigned long ints, I guess I can just store all
  22. >31 powers of 2 in a table and compare to n.  Though I don't know a fast
  23. >algorithm to compare a number to 31 numbers in an array.
  24.  
  25. >Perhaps there is a tricky nonportable way to see if I have power-of-2 by 
  26. >looking at bits?  (That is fine for this application)
  27. How about a tricky portable way...
  28. For unsigned integers, a value that is a power of two will consist of only one 
  29. '1' bit and a lot of '0' bits. The following table illustrates this 
  30. observation.   2^0 == 1 == b'00001'
  31.                        2^1 == 2 == b'00010'
  32.                        2^2 == 4 == b'00100'
  33.                        2^3 == 8 == b'01000'
  34. etcetera
  35.  
  36. /* is_power_of_2() returns 0 if num is not a power of 2, and 1 if it is */
  37. int is_power_of_2(num)
  38. unsigned long num;
  39. {
  40.      int bitcount;  /* assume no more than MAX_INT bits in longint*/       
  41.  
  42.     for (bitcount = 0; num; num >>= 1)
  43.           if (n&1) ++ bitcount;    
  44.     return (bitcount == 1) ? 1 : 0;
  45. }
  46.  
  47. >Thanks very much for any help.
  48.  
  49. You're welcome
  50.  
  51. >Bill Simpson
  52.  
  53.  
  54. Lew Pitcher             | "I'm a little source code
  55. Toronto Dominion Bank   |  Short and Stout
  56. =======================    |  Here is my Input,
  57. Enzo Matrix - Reboot    |  And here is my out"
  58.